//给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
//
// 叶子节点 是指没有子节点的节点。
//
// 示例 1：
//
//
//输入：root = [1,2,3,null,5]
//输出：["1->2->5","1->3"]
//
//
// 示例 2：
//
//
//输入：root = [1]
//输出：["1"]
//
//
//
//
// 提示：
//
//
// 树中节点的数目在范围 [1, 100] 内
// -100 <= Node.val <= 100
//
//
// Related Topics 树 深度优先搜索 字符串 回溯与递归 二叉树 👍 914 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
//? 递归
function binaryTreePaths(root: TreeNode | null): string[] {

    function traverse(root, route) {
        if (root === null) return
        route += root.val
        if (!root.left && !root.right) res.push(route)
        traverse(root.left, route + '->')
        traverse(root.right, route + '->')

    }
    let res : string[] = []
    if (root === null) return res
    traverse(root, "")
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
//? 迭代
function binaryTreePaths2(root: TreeNode | null): string[] {
    let helperStack: TreeNode[] = [];
    let tempNode: TreeNode;
    let routeArr: string[] = [];
    let resArr: string[] = [];
    if (root !== null) {
        helperStack.push(root);
        routeArr.push(String(root.val));
    };
    while (helperStack.length > 0) {
        //? 一个栈记录当前节点，一个栈记录路径（不断更新）
        tempNode = helperStack.pop()!;
        let route: string = routeArr.pop()!; //? tempNode 对应的路径
        if (tempNode.left === null && tempNode.right === null) {
            resArr.push(route);
        }
        if (tempNode.right !== null) {
            helperStack.push(tempNode.right);
            routeArr.push(route + '->' + tempNode.right.val);   //? tempNode.right 对应的路径,入栈
        }
        if (tempNode.left !== null) {
            helperStack.push(tempNode.left);
            routeArr.push(route + '->' + tempNode.left.val);    //? tempNode.left 对应的路径,入栈
        }
    }
    return resArr;
};
